package com.maltys.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/restore-ip-addresses/">复原ip地址</a>
 */
public class IpAddressRecovery {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        backTracing(s, 0, new ArrayList<>(), res);
        return res;
    }

    private void backTracing(String origin, int idx, List<String> ipPartition, List<String> res) {
        if (idx < origin.length() && ipPartition.size() >= 4) {
            return;
        }

        if (ipPartition.size() == 4) {
            res.add(String.join(".", ipPartition));
            return;
        }

        for (int i = idx; i < origin.length(); i++) {
            String sub = origin.substring(idx, i + 1);
            if (!isValidIpPartition(sub)) {
                break;
            }
            ipPartition.add(sub);
            backTracing(origin, i + 1, ipPartition, res);
            ipPartition.remove(ipPartition.size() - 1);
        }
    }

    private boolean isValidIpPartition(String sub) {
        if (sub.startsWith("0") && sub.length() > 1) {
            return false;
        }
        int ipPartition = Integer.parseInt(sub);
        return ipPartition <= 255 && ipPartition >= 0;
    }

    public static void main(String[] args) {
        IpAddressRecovery ipAddressRecovery = new IpAddressRecovery();
        List<String> list = ipAddressRecovery.restoreIpAddresses("101023");
        System.out.println(list);
    }
}
